Since their first development in the 1960's, Reed-Solomon codes and BCH codes have been widely defined and used in many communication systems and data storage systems (such as DVD, flash memory or digital video, etc.) to serve as an error correction mechanism. Especially, due to its relative long block length of the shortened BCH codes, it has become a major challenge to design a decoder—in order to fulfill high performance and high transmission requirements—which is capable of completing, in a short period of time, the decoding process for the shortened BCH code defined in DVB-S2.
For the prior-art technique, the decoding process of BCH codes mainly consists of three steps: calculating syndrome, solving the key equation, and Chien search, such as the structure shown in FIG. 1(a). The syndrome calculator computes coefficients Sj for xj−1 in the syndrome polynomial S(x), where j=1, 2, . . . , 2t; then the key equation solver resolves an error location polynomial σ(x); and finally all the roots of the polynomial σ(x) are found by using the Chien search in order to further identify error locations. For the known art in the field of Reed-Solomon decoding, decoding steps are similar to BCH decoding, which are mainly consisted of four steps as shown in FIG. 1(b): calculating syndrome, solving the key equation, Chien search and calculating error values. The main operations of the syndrome calculator and Chien search shown in FIG. 1 are both finite-field constant multiplication such as the one shown in FIG. 2. The part of syndrome computation includes 2t syndrome computation cells as shown in FIG. 2, in which 2t syndromes are generated respectively by these 2t syndrome computation cells after n cycles. On the other hand, a Chien search circuit consists of t Chien search cells as shown in FIG. 2. Initially, the operation begins by selecting 0 as an input, and then in each of the subsequent cycles, the inputs are all σi, while in each cycle a finite-field element is checked to see whether it is a root of σ(x). The Chien search is then completed at n-th cycle. However, because two different cells have respective different inputs which have to be calculated and processed by different circuit configurations, hardware complexity is increased accordingly.
Prior art in this field includes: Patent Application 1, Howard H. Ireland et al, “Method and Apparatus for use in a decoder of a forward error correction (FEC) system for locating bit errors in a error locator polynomial,” U.S. Pat. No. 7,058,876 B1, Jun. 6, 2006; and Literature 1, G. Davida and J. Cowles, “A new error-locating polynomial for decoding of BCH codes,” IEEE Trans. Inform. Theory, Vol. 21, pp. 235-236, March 1975; Literature 2, Y. Chen and K. K. Parhi, “Area-efficient parallel decoder architecture for long BCH codes,” IEEE International Conference on Acoustic, Speech, and Signal Processing, Vol. 5, pp. v-73-6, May, 2004.
However, the above mentioned prior art has its drawback in different respect. For example, in Patent Application 1, only an improvement for searching error locations in Chien search is provided; in Literature 1, only the definition of a reverse error location polynomial and its corresponding Berlekamp-Massey algorithm is provided without mentioning its corresponding decoder architecture and achievable performance improvement; and in Literature 2, only a Chien searching architecture for a BCH decoder that is adapted for decoding a code having relatively long code-length is provided. Its parallel operation architecture is capable of improving decoding time for long codes, while much more hardware complexity is needed. However, in both literatures, how to use the Berlekamp-Massey decoding algorithm corresponding to the reverse error location polynomial in order to jointly use part of the circuits for the syndrome calculator and Chien search as well as their corresponding parallel operation architecture so as to achieve the objective of reducing hardware cost or improving decoding rate is not discussed.